#include<stdio.h>
#include<stdbool.h>
struct ListNode {
    int val;
    struct ListNode* next;
    //ListNode(int x) : val(x), next(NULL) {}
}; 
typedef struct ListNode ListNode;
ListNode* partition(ListNode* pHead, int x) 
{
    ListNode* lhead = NULL;
    ListNode* ltail = NULL;
    ListNode* bhead = NULL;
    ListNode* btail = NULL;
    ListNode* cur = pHead;
    while (cur != NULL)
    {
        if (cur->val < x)
        {
            if (lhead == NULL)
            {
                lhead = ltail = cur;
            }
            else
            {
                ltail->next = cur;
                ltail = cur;
            }
            cur = cur->next;
        }
        else
        {
            if (bhead == NULL)
            {
                bhead = btail = cur;
            }
            else
            {
                btail->next = cur;
                btail = cur;
            }
            cur = cur->next;
        }
    }
    if (lhead == NULL)
        return bhead;
    if (bhead == NULL)
        return lhead;
    btail->next = NULL;
    ltail->next = bhead;
    return lhead;
}

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
    int a = 0;
    int b = 0;
    ListNode* cur = headA;
    ListNode* fast = NULL;
    ListNode* slow = NULL;
    while (cur != NULL)
    {
        a++;
        cur = cur->next;
    }
    cur = headB;
    while (cur != NULL)
    {
        b++;
        cur = cur->next;
    }
    if (a > b)
    {
        fast = headA;
        slow = headB;
    }
    else
    {
        fast = headB;
        slow = headA;
    }
    int n = (a - b) > 0 ? (a - b) : (b - a);
    while (n--)
    {
        fast = fast->next;
    }
    while (fast != NULL && slow != NULL)
    {
        if (fast == slow)
        {
            return fast;
        }
        else
        {
            fast = fast->next;
            slow = slow->next;
        }
    }
    return NULL;
}
bool hasCycle(struct ListNode* head) 
{
    ListNode* fast, * slow, * meet;
    fast = head;
    slow = head;
    meet = NULL;
    while (fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            meet = slow;
            break;
        }
    }
    if (fast == NULL || fast->next == NULL)
    {
        return NULL;
    }
    slow = head;
    while (slow != meet)
    {
        slow = slow->next;
        meet = meet->next;
    }
    return slow;
}

int main()
{

	return 0;
}

